/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  let res = new Array(n + 1).fill(0)
  //利用状态转移方程res[i] = res[i >> 1] + (i & 1)，对数组的每一位元素进行处理（统计该元素二进制中1的个数）
  /* 举个例子：i = 5（二进制是 101）
     i >> 1 = 2（101 右移一位，二进制变为 10，相当于除以二再向下取整）
     res[2] 的结果是 1（调用前面已经计算出来的状态：2的二进制10中有一个1，即res[2]为1）
     5 & 1 的结果是 1（判断被移除位的数字是不是1：101 的最低位是 1，即101&1为1）
  */
  for (let i = 1; i <= n; i++) {
    res[i] = res[i >> 1] + (i & 1)
  }
  return res
};